public class _01 {

/*
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
*/

    public static void main(String[] args) {
//        int a [] = {1,2,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,9,9,9,9,10};
        int a[] = {1, 2, 3, 4, 5, 6, 7};
        int b[] = Solution.searchRange(a, 7);
        for (int t : b) {
            System.out.print(t + " ");
        }
    }

    class Solution {
        //循环遍历
//    public int[] searchRange(int[] nums, int target) {
//        int a = -1 , b = -1;
//        for(int i = 0; i <nums.length; i++){
//            if(nums[i] == target && a == -1){
//                a = i ;
//            }
//            if(i == nums.length -1 && nums[i] == target && a != -1 && b == -1){
//                b = i ;
//            }
//            if(nums[i] > target && a != -1 && b == -1){
//                b = i - 1;
//            }
//        }
//        int result [] ={a, b };
//        return result;
//    }

        //二分查找
        public static int[] searchRange(int[] nums, int target) {
            int a = search(nums, target);
            int b = search(nums, target + 1);
            if (a == b) {
                a = -1;
                b = -1;
            } else {
                b--;
            }
            int result[] = {a, b};
            return result;
        }

        public static int search(int[] a, int x) {
            int l = 0, r = a.length, m;
            while (l < r) {
                m = (l + r) >> 1;
                if (a[m] < x) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            return l;
        }
    }
}

